package 树;

import 动态数组.线性表.ArrayList;
import 动态数组.线性表.List;
import 动态链表.LinkedList;
import 集合.LinkedSet;
import 集合.TreeSet;
import 集合.接口.Map;
import 集合.接口.Set;

import java.util.Iterator;

public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> {

    private class Node{
        public K key;
        public V value;
        public int height;
        public Node left,right;
        public Node(K key,V value){
            this.key = key;
            this.value = value;
            this.left = this.right = null;
            this.height = 1;
        }
    }

    private Node root;
    private int size;

    public AVLTreeMap(){
        root = null;
        size = 0;
    }

    //查找搜索树查找以k为值的节点
    private Node getNode(Node node,K key){
        if (node == null){
            return null;
        }
        if (key.compareTo(node.key) < 0){
            return getNode(node.left,key);
        }else if (key.compareTo(node.key) > 0){
            return getNode(node.right,key);
        }else {
            return node;
        }
    }

    //获取节点的高度
    private int getHeight(Node node){
        if (node == null){
            return 0;
        }
        return node.height;
    }

    //获取平衡因子
    private int getBalanceFactory(Node node){
        if (node == null){
            return 0;
        }
        return getHeight(node.left) - getHeight(node.right);
    }

    //验证二分搜索树是否为二分搜索树
    public boolean isBST(){
        //中序遍历，搜素树为一个升序排列，判断中序遍历后的数据是否为升序
        ArrayList<K> keys = new ArrayList<>();
        inOrder(root,keys);
        for (int i = 0; i < keys.size() - 1; i++) {
           if (keys.get(i).compareTo(keys.get(i + 1)) > 0){
               return false;
           }
        }
        return true;
    }

    private void inOrder(Node node, ArrayList<K> keys) {
        if (node == null){
            return;
        }
        inOrder(node.left,keys);
        keys.add(node.key);
        inOrder(node.right,keys);
    }

    //验证当前的二分搜索树为平衡的
    public boolean isBalance(){
        return isBalance(root);
    }

    private boolean isBalance(Node node) {
        if (node == null){
            return true;
        }
        int balanceFactory = getBalanceFactory(node);
        if (Math.abs(balanceFactory) > 1){
            return false;
        }

        return isBalance(node.left) && isBalance(node.right);
    }


    //右旋转，将当前的节点向下移，并返回新树的根
    public Node rightRotate(Node y){
        Node x = y.left;
        Node T3 = x.right;
        x.right = y;
        y.left = T3;
        y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
        return  x;
    }

    //左旋，将当前的节点向下移，并返回新树的根
    public Node leftRotate(Node y){
        Node x = y.right;
        Node T3 = x.left;
        x.left = y;
        y.right = T3;
        y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
        return  x;
    }

    @Override
    public void put(K key, V value) {
        root = put(root,key,value);

    }

    private Node put(Node node, K key, V value) {
        if (node == null){
            size++;
            return new Node(key,value);
        }
        if (key.compareTo(node.key) < 0){
            node.left = put(node.left,key,value);
        }else if (key.compareTo(node.key) > 0){
            node.right = put(node.right,key,value);
        }else {
            node.value = value;
        }
        //添加一个entry后要更新该树的高度和其平衡性
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        //获取该树的平衡因子，判断该数是否为一个平衡数
        int balanceFactory = getBalanceFactory(node);

        //左侧的左侧不平衡,>1表示左子树和右子树的高度差大于1，>=0表示当前树的左子树有值
        if (balanceFactory > 1 && getBalanceFactory(node.left) >= 0){
            //右旋转
            return rightRotate(node);
        }

        //左侧的右侧,>1表示左子树和右子树的高度差大于1，0<表示当前树的右子树有值
        if (balanceFactory >1 && getBalanceFactory(node.left) < 0){
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        //右侧的左侧,>=0表示右子树的左侧有值
        if (balanceFactory < -1 && getBalanceFactory(node.right) >= 0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        //右侧的右侧,0< 表示该节点的右侧有值
        if (balanceFactory < -1 && getBalanceFactory(node.right) < 0){
            return leftRotate(node);
        }
        return node;
    }

    @Override
    public V remove(K key) {
        Node delNode = getNode(root,key);
        if (delNode != null){
            root = remove(root,key);
            return delNode.value;
        }
        return null;
    }

    private Node remove(Node node, K key) {
        if (node == null){
            return null;
        }
        Node retNode;
        if (key.compareTo(node.key) < 0){
            node.left = remove(node.left,key);
            retNode = node;
        }else if (key.compareTo(node.key) > 0){
            node.right = remove(node.right,key);
            retNode = node;
        }else {
            //左边为空,右边不为空
            if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                retNode = rightNode;
            }else if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                retNode = leftNode;
            }else {
                //左右都不为空
                //查右子树的最小的值
                Node s = minimum(node.right);
                //移除最小的节点,给最小值的右边接上
                s.right = removeMin(node.right);
                s.left = node.left;
                node.left = node.right = null;
                retNode = s;
            }

        }
        //更新树的高度，并使该树为一颗平衡树
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        //获取平衡因子
        int balanceFactory = getBalanceFactory(node);
        //左侧的左侧不平衡,>1表示左子树和右子树的高度差大于1，>=0表示当前树的左子树有值
        if (balanceFactory > 1 && getBalanceFactory(node.left) >= 0){
            //右旋转
            return rightRotate(node);
        }

        //左侧的右侧,>1表示左子树和右子树的高度差大于1，0<表示当前树的右子树有值
        if (balanceFactory >1 && getBalanceFactory(node.left) < 0){
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        //右侧的左侧,>=0表示右子树的左侧有值
        if (balanceFactory < -1 && getBalanceFactory(node.right) >= 0){
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        //右侧的右侧,0< 表示该节点的右侧有值
        if (balanceFactory < -1 && getBalanceFactory(node.right) < 0){
            return leftRotate(node);
        }

        return null;
    }

    private Node removeMin(Node node) {
        if (node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        return removeMin(node.left);
    }

    private Node minimum(Node node) {
        if (node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    @Override
    public boolean contains(K key) {
        return getNode(root,key) != null;
    }

    @Override
    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    @Override
    public V set(K key, V value) {
        Node node = getNode(root, key);
        if (node == null){
            throw new IllegalArgumentException("not found!");
        }
        V ret = node.value;
        node.value = value;
        return ret;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0 && root == null;
    }

    @Override
    public Set<K> keySet() {
        TreeSet<K> set = new TreeSet<>();
        inOrderKeySet(root,set);
        return set;
    }

    private void inOrderKeySet(Node node, TreeSet<K> set) {
        if (node == null){
            return;
        }
        inOrderKeySet(node.left,set);
        set.add(node.key);
        inOrderKeySet(node.right,set);
    }


    @Override
    public List<V> values() {
        LinkedList<V> list = new LinkedList<>();
        inOrderValue(root,list);
        return list;
    }

    private void inOrderValue(Node node, LinkedList<V> list) {
        if (node == null){
            return;
        }
        inOrderValue(node.left,list);
        list.add(node.value);
        inOrderValue(node.right,list);
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        LinkedSet<Entry<K,V>> set = new LinkedSet<>();
        inOrderEntrySet(root,set);
        return set;
    }

    private void inOrderEntrySet(Node node, LinkedSet<Entry<K, V>> set) {
        if (node == null){
            return;
        }
        inOrderEntrySet(node.left,set);
        set.add(new AVLTreeEntry<>(node.key,node.value));
        inOrderEntrySet(node.right,set);
    }

    private class AVLTreeEntry<K,V> implements Entry<K,V>{
        private K key;
        private V value;

        public AVLTreeEntry(K key,V value){
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return key;
        }

        @Override
        public V getValue() {
            return value;
        }
    }

    @Override
    public String toString() {
        LinkedSet<Entry<K,V>> set = (LinkedSet<Entry<K, V>>) entrySet();
        StringBuilder sb = new StringBuilder();
        sb.append('[');
        if (isEmpty()){
            sb.append(']');
        }else {
            for (Entry<K, V> entry : set) {
                sb.append('(');
                sb.append(entry.getKey());
                sb.append(':');
                sb.append(entry.getValue());
                sb.append(')');
                sb.append(',');
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(']');
        }
       return sb.toString();
    }

    @Override
    public Iterator<Entry<K,V>> iterator() {
        return new AVLIterator();
    }



    private class AVLIterator implements Iterator<Entry<K,V>>{
        private TreeSet<K> keys;
        public AVLIterator(){
            keys = new TreeSet<>();
        }

        @Override
        public boolean hasNext() {
            return !keys.isEmpty();
        }

        @Override
        public Entry<K, V> next() {
            K key = keys.removeMin();
            return new AVLTreeEntry<>(key,getNode(root,key).value);
        }
    }
}
